package Queue;

import LinkedList.ListNode;

import java.util.LinkedList;

/**
 *  题目 ： 设计循环队列
 *  题目详述 ：
 *  设计你的循环队列实现。
 *  循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。
 *  它也被称为“环形缓冲器”。
 *  循环队列的一个好处是我们可以利用这个队列之前用过的空间。
 *  在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。
 *  但是使用循环队列，我们能使用这些空间去存储新的值。
 *
 * 你的实现应该支持如下操作：
 * MyCircularQueue(k): 构造器，设置队列长度为 k 。
 * Front: 从队首获取元素。如果队列为空，返回 -1 。
 * Rear: 获取队尾元素。如果队列为空，返回 -1 。
 * enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
 * deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
 * isEmpty(): 检查循环队列是否为空。
 * isFull(): 检查循环队列是否已满。
 */
public class MyCircularQueue {
    /**
     *  方法一 ：数组
     *
     *  核心思想 ：模拟数组，来构建循环队列
     *  主要在与区分循环队列为空，还是循环队列为满；（通过构建 比队列元素数量 + 1的数组 来区分循环队列为空还是为满）
     *  （1）循环队列为空的话，即，头指针front == 尾指针rear
     *  （2）循环队列满的话，即，队列判满的条件是 front == （rear + 1） mod 循环队列长度
     */
    /*
    private Integer front;
    private Integer rear;
    private int[] array;
    private int arrayLength;
    public MyCircularQueue(int k) {
        // 初始化
        front = 0;
        rear = 0; // rear,指向的是队列尾元素对应的索引的下一个索引（即，指向的是下一个存储值的索引）
        arrayLength = k + 1;
        array = new int[arrayLength];
    }
    // 向循环队列中插入元素
    public boolean enQueue(int value) {
        if(isFull()){
            return false;
        }
        System.out.println(rear);
        array[rear] = value;
        // 需要保证尾指针所存储的值小于arrayLength
        rear = (rear + 1) % arrayLength;
        // 特殊情况 ：即，front头指针所指向的并不是0；即，出现了循环队列的长度超过了数组的长度
        return true;
    }
    // 删除循环队列中的元素
    // （注意 ：队列是从队首开始删除元素！！！）
    public boolean deQueue() {
        if(isEmpty()){
            return false;
        }
        front = (front + 1) % arrayLength;
        return true;
    }

    public int Front() {
        if(isEmpty()){
            return -1;
        }
        // 由于返回的是front头指针，头指针所指向的值即为队列中的头元素；
        // 所以，没有必要去考虑模拟队列的数组索引出现不存在的情况；
        return array[front];
    }

    public int Rear() {
        if(isEmpty()){
            return -1;
        }
        // 由于rear尾指针所指向的是队尾元素的后一个索引
        // 特殊情况 ：
        // rear指针经过一圈push之后，变为0；在此情况下，若是return array[rear - 1],即会出现return array[-1]的情况
        System.out.println(array[(rear - 1 + arrayLength) % arrayLength]);
        return array[(rear - 1 + arrayLength) % arrayLength];
    }

    public boolean isEmpty() {
        return front == rear;
    }

    public boolean isFull() {
        return front == (rear + 1) % arrayLength;
    }
     */
    /**
     *  方法二 ：链表（推荐）
     *
     *  核心思想 ：使用链表来模拟队列
     *  （1） 头节点head和尾节点tail分别指向队列的队首元素和队尾元素
     *  （2） 同时，引入变量length，指向的是队列的长度；
     *  （3） 引入变量size，指的是当前链表的长度（初始长度为0）
     *  （4） 队列为空的判断条件是，size == 0；队列为满的判断条件是，size == length
     */
    // 头尾指针分别指向 队列的头元素和为元素
    private ListedNode head;
    private ListedNode tail;
    private Integer length; // 队列的长度（即，其队列的最大容量）
    private Integer size; // 当前链表的长度
    public MyCircularQueue(int k) {
        // 初始化
        length = k;
        size = 0;
    }

    public boolean enQueue(int value) {
        if(isFull()){
            return false;
        }
        // 初始化一个节点（节点存储所需要加入队列的value）
        ListedNode node = new ListedNode(value);
        if(isEmpty()){
            // 若是队列为空的话，则使得头节点和尾节点都指向新插入的节点
            head = tail = node;
        }
        else {
            // (1)若是队列不为空的话，头节点head不需要任何操作
            // (2)由于tail尾指针所指向的是队列尾部元素，所以需要使得tail.next = node
            // (3)同时将尾指针tail向后移（即，指向新插入的节点）

            tail.next = node;  // 尾指针所指向的节点，在其后面连接上新插入的系欸但
            tail = node;    // 尾指针指向刚刚新插入的节点
        }
        size++; // 链表长度 + 1
        return true;
    }

    public boolean deQueue() {
        if(isEmpty()){
            return false;
        }
        // 舍弃队列中的队首元素 ：直接将头指针指向其的next节点即可
        head = head.next;
        size--; // 链表长度 - 1
        return true;
    }

    public int Front() {
        if(isEmpty()){
            return -1;
        }
        return head.value;
    }

    public int Rear() {
        if(isEmpty()){
            return -1;
        }
        return tail.value;
    }

    public boolean isEmpty() {
        // 即，链表长度为0的话，等价于队列为空
        return size == 0;
    }

    public boolean isFull() {
        // 即，链表的长度与初始化所获取的队列长度一致的话，等价于队列已经满了
        return size == length;
    }

    class ListedNode{
        private ListedNode next;
        private Integer value;
        public ListedNode(int value){
            this.value = value;
        }
    }
}
